//给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "abab"
//输出: true
//解释: 可由子串 "ab" 重复两次构成。
// 
//
// 示例 2: 
//
// 
//输入: s = "aba"
//输出: false
// 
//
// 示例 3: 
//
// 
//输入: s = "abcabcabcabc"
//输出: true
//解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
// 
//
// 
//
// 提示： 
//
// 
//
// 
// 1 <= s.length <= 10⁴ 
// s 由小写英文字母组成 
// 
// Related Topics 字符串 字符串匹配 👍 654 👎 0

package leetcode.editor.cn;

class RepeatedSubstringPattern {
    public static void main(String[] args) {
        Solution solution = new RepeatedSubstringPattern().new Solution();
        solution.repeatedSubstringPattern("bb");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
    /*public boolean repeatedSubstringPattern(String s) {
        if (s.length() == 0) {
            return false;
        }

        int len = s.length();
        int j = 0;
        int[] next = new int[len];
        next[0] = 0;

        for (int i = 1; i < len; i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }

            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }

            next[i] = j;
        }

        if (next[len - 1] != 0 && (len % (len - next[len - 1])) == 0) {
            return true;
        }

        return false;
    }*/

        /*public boolean repeatedSubstringPattern(String s) {
            if (s.length() == 0) {
                return false;
            }

            int j = -1;
            int len = s.length();
            int[] next = new int[len];
            next[0] = j;
            for (int i = 1; i < len; i++) {
                while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
                    j = next[j];
                }

                if (s.charAt(i) == s.charAt(j + 1)) {
                    j++;
                }

                next[i] = j;
            }

            // 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
            if (next[len - 1] > 0 && (len % (len - (next[len - 1] + 1))) == 0) {
                return true;
            }

            return false;
        }*/

        public boolean repeatedSubstringPattern(String s) {
            int n = s.length();
            int[] next = new int[n];
            int j = -1;
            next[0] = j;
            for (int i = 1; i < n; i++) {
                while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
                    j = next[j];
                }

                if (s.charAt(i) == s.charAt(j + 1)) {
                    j++;
                }

                next[i] = j;
            }

            if (next[n - 1] != -1 && n % (n - (next[n - 1] + 1)) == 0) return true;

            return false;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
